package com.example.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 单调栈
 * 给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。
 * 现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
 *
 * 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组
 */
public class Demo0321 {
    public static void main(String[] args) {
        int [] nums1=new int[]{3,4,6,5};
        int [] nums2=new int[]{9,1,2,5,8,3};
        maxNumber(nums1,nums2,5);
    }

    public static int[] maxNumber(int[] nums1, int[] nums2, int k) {

        int len1 = nums1.length;
        int len2 = nums2.length;

        int [] curMax=new int[k];
        for (int i = 0; i <= k; i++) {
            //1.长度不够跳过
            if (i>len1 || k-i>len2){
                continue;
            }
            //2.获取每个数组最大
            int[] max1 = getMax(nums1, i);
            int[] max2 = getMax(nums2, k-i);

            //3.merge
            int[] cur = merge(max1, max2);

            //4.判断大小
            if (greater(cur,curMax,0,0)){
                curMax=cur;
            }

        }
        return curMax;
    }

    //比字典序大小
    private static boolean greater(int[] cur, int[] curMax, int idx1, int idx2) {
        int len1 = cur.length;
        int len2 = curMax.length;
        while (idx1<len1 && idx2<len2 && cur[idx1]==curMax[idx2]){
            idx1++;
            idx2++;
        }
        return idx2==len2 || ((idx1<len1) && cur[idx1]>curMax[idx2]) ;
    }

    private static int[] merge(int[] max1, int[] max2) {
        int len1 = max1.length;
        int len2 = max2.length;
        int len =len1+len2;
        int [] res=new int[len];
        int idx=0,idx1=0,idx2=0;
        while (idx1<len1 || idx2< len2){
            if (greater(max1,max2,idx1,idx2)){
                res[idx++]=max1[idx1++];
            }else {
                res[idx++]=max2[idx2++];
            }
        }
        return res;
    }

    private static int[] getMax(int[] nums1, int num) {
        Deque<Integer> stack=new ArrayDeque<>();
        stack.addFirst(9);
        int len=nums1.length;
        for (int i = 0; i < len; i++) {
            int temp=nums1[i];
            //1.考虑出栈
            while (stack.peekLast()<temp && stack.size()+len-i>(num+1)){
                stack.removeLast();
            }
            //2.入栈
            stack.addLast(temp);
        }

        //截取长度 && 移除哨兵
        while (stack.size()>(num+1)){
            stack.removeLast();
        }
        stack.removeFirst();

        int [] res=new int[num];
        for (int i = 0; i < num; i++) {
            res[i]=stack.pollFirst();
        }
        return res;
    }
}
